package cn.njupt.cmpSort;

public class QuickSort1<E extends Comparable<E>> extends Sort<E> {


    @Override
    public void sort() {
        sort(0,array.length);
    }

    private void sort(int begin, int end) {
        if(end-begin<2)return;

        int pivotIndex=partSort(begin,end);
        sort(begin,pivotIndex);
        sort(pivotIndex+1,end);
    }

    private int partSort(int begin, int end) {
        end--;
        E pivot=array[begin];
        while (begin<end){
            while(begin<end){
                if(cmpElements(pivot,array[end])<0){
                    end--;
                }else{  //pivot>=array[end]
                    array[begin]=array[end];   //array[end]=没有变;
                    begin++;
                    break;
                }
            }
            while(begin<end) {
                if (cmpElements(pivot, array[begin]) > 0) {
                    begin++;
                } else {  //pivot<=array[begin]
                    array[end] = array[begin];
                    end--;
                    break;
                }
            }
        }
        array[begin]=pivot;
        return begin;
    }
}
